//
// 线索二叉树
// Created by 麻再挺 on 2021/12/14.
//

#ifndef DATA_STRUCTURE_C_BI_THR_TREE_H
#define DATA_STRUCTURE_C_BI_THR_TREE_H

#include <stdio.h>
#include <stdlib.h>
#include "./../constant.h"

/**
 * 指针标识
 * LINK: 指针
 * THREAD: 线索
 */
typedef enum PointerTag {
    LINK,
    THREAD
};

// 类型
typedef char TElemType;

/**
 * 线索二叉树
 */
typedef struct BiThrNode {
    // 数据
    TElemType data;
    // 左右孩子指针
    struct BiThrNode *lChild, *rChild;
    // 左右标识
    enum PointerTag lTag, rTag;
} BiThrNode, BiThrTree;

/**
 * 按先序次序输入二叉树中结点的值, 空格字符表示空树
 * @param t 二叉树
 * @return
 */
Status CreateBiThrTree(BiThrTree *t);

/**
 * 将二叉树按中序线索化
 * @param t 二叉树
 * @return
 */
Status InOrderThreading(BiThrTree *thrTree, BiThrTree *t);

/**
 * 中序遍历
 */
Status InOrderThrTraverse(BiThrTree *t);

/**
 * 层序遍历
 */
Status LevelOrderThrTraverse(BiThrTree *t);

#endif //DATA_STRUCTURE_C_BI_THR_TREE_H
